package pers.vic.basics.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @description:406. 根据身高重建队列 {@literal https://leetcode-cn.com/problems/queue-reconstruction-by-height/}
 * @author Vic.xu
 * @date: 2020/11/16 0016 8:33
 */
public class J0406_M_ReconstructQueue {
    /*
    假设有打乱顺序的一群人站成一个队列。
    每个人由一个整数对(h, k)表示，其中h是这个人的身高，
    k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
    注意：
    总人数少于1100人。
    输入:
     [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

    输出:
    [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
     */

    /**
     * 1. 原来是有序的
     * 2. 先按照身高降序，k升序排序
     * [7, 0]->[7, 1]->[6, 1]->[5, 0]->[5, 2]->[4, 4]
     * 3.然后按照这个二维数组内部的k的顺序插入ArrayList
     * [5, 0]->[7, 0]->[5, 2]->[6, 1]->[4, 4]->[7, 1]
     *
     * @param people
     * @return
     */
    public static int[][] reconstructQueue(int[][] people) {
        print(people);
        //先按照身高降序，k升序排序
        Arrays.sort(people, (i, j) -> i[0] == j[0] ? (i[1] - j[1]) : (j[0] - i[0]));
        print(people);
        //然后按照这个二维数组内部的k的顺序插入ArrayList
        ArrayList<int[]> result = new ArrayList<>();
        for (int[] person : people) {
            result.add(person[1], person);
            for (int[] ints : result) {
                System.out.print("[" +ints[0]+","+ ints[1]+ "]\t");
            }
            System.out.println();
        }
        return result.toArray(people);
    }

    public static void main(String[] args) {
        int[][] people = {{7,0}, {4,4}, {7,1}, {5,0},{6,1}, {5,2}};
        int[][] ints = reconstructQueue(people);
        print(ints);
    }
    private static void print(int[][] people){
        String string = Stream.of(people).map(Arrays::toString).collect(Collectors.joining("->"));
        System.out.println(string);
    }
}
